本文内容由简易程序从latex批量转义而来, 排版并不友好, 相对精美版请见课程整理

第三次作业

习题四 13

解:

• \(R_1 \circ R_2=\{(1,4),(1,3)\}\)
• \(R_2 \circ R_1=\{(3,4)\}\)
• \(R_1\circ R_2\circ R_1=\varnothing\)
• \(R_1^3=\{(1,1),(1,4)\}\)

习题四 15

解:

• \(A\) 非空, 则 \(\exists\ a \in A\) 取 \(R_1=\varnothing,R_2=\{(a,a)\}\).

习题四 16

解:

• $
  \forall (a,b) \in R\cap \widetilde{R} \Rightarrow (a,b) \in R \wedge (a,b) \in \widetilde{R} \\ \Rightarrow (a,b) \in R \wedge (b,a) \in R \Rightarrow a=b.
  $
  由此说明 \(R \cap \widetilde{R}\) 中只有对角线可能非零, 即非零元素个数不超过 \(n\).

习题四 17

解:

• (1) 真, \(\forall a \in A, (a,a) \in R_1 \cap (a,a) \in R_2 \Rightarrow (a,a) \in R_1 \circ R_2\).
  (2) 假, 取 \(R_1=\{(1,2)\},R_2=\{(2,1)\}\Rightarrow R_1 \circ R_2=\{(1,1)\}\) 不是反自反的.
  (3) 假, 取 \(R_1=\{(1,2),(2,1)\},R_2=\{(2,3),(3,2)\}\Rightarrow R_1\circ R_2=\{(1,3)\}\).
  (4) 假, 取 \(R_1=\{(1,3),(2,3)\},R_2=\{(3,1),(3,2)\}\Rightarrow R_1\circ R_2=\{(1,1),(2,2),(1,2),(2,1)\}\).
  (5) 假, 取 \(R_1=\{(1,4),(2,5)\},R_2=\{(4,2),(5,3)\}\Rightarrow R_1\circ R_2=\{(1,2),(2,3)\}\).

习题四 18

证明

• 由 \(R^+\circ R^+=R^+ \Rightarrow (R^+)^+=\bigcup (R^+)^k=R^+\).

  同理 \(R^*\circ R^*=R^*\Rightarrow (R^*)^*=R^*\).

习题四 19

(1)

**证明**

-   由 $(1,2),(2,4) \in R,(1,4) \notin R\Rightarrow R$ 不是传递关系 .

(2)

**解:**

-   $R_1=\{(1,2),(1,3),(1,4),(2,4),(2,3),(3,4),(4,3),(3,3)\}$.

(3) 存在, 全关系.

习题四 20

(1)

**证明**

-   自反: $\forall (a,b) \in A\times A,a+b=b+a\Rightarrow ((a,b),(a,b)) \in R$.
    对称: $\forall ((a,b),(c,d))\in R,a+d=b+c \Rightarrow c+b=d+a\Rightarrow ((c,d),(a,b)) \in R$.
    传递: $\forall ((a,b),(c,d)),((c,d),(e,f))\in R,a+d=b+c,c+f=d+e\Rightarrow a-b=c-d=e-f\Rightarrow a+f=e+b\Rightarrow((a,b),(e,f))\in R$.

(2) \([(2,5)]_R=\{(1,4),(2,5),(3,6),(4,7),(5,8)\}\).

(3) 不对, \(R\) 中的元素形式为 \(((a,b),(c,d))\) 而 \(A\times A\) 中的元素形式为 \((a,b)\), 应该说 \(R\subseteq (A\times A)\times(A\times A)\).

习题四 23

(1)

**证明**

-   自反: $\forall a \in A, (a,a)\in R_1\wedge(a,a) \in R_2\Rightarrow (a,a)\in R_1 \cap R_2$.

    对称: $\forall (a,b) \in R_1 \cap R_2,(a,b) \in R_1\wedge (a,b)\in R_2\Rightarrow (b,a) \in R_1\wedge (b,a)\in R_2\\
    \Rightarrow (b,a) \in R_1 \cap R_2$.

    传递: $\forall (a,b),(b,c) \in R_1\cap R_2,(a,b),(b,c) \in R_1\Rightarrow (a,c) \in R_1$, 同理 $(a,c) \in R_2$, 故 $(a,c) \in R_1\cap R_2$.

(2) 取 \(R_1=\{(1,1),(2,2),(3,3),(1,2),(2,1)\},R_2=\{(1,1),(2,2),(3,3),(2,3),(3,2)\}\).

习题四 28

\begin{tikzpicture}
\graph {
1 <-> 2;
1 <-> 3;
1 ->[loop above] 1;
2 ->[loop above] 2;
3 ->[loop left] 3;
2 <-> 3;
4 ->[loop above] 4;
5 <-> 6;
5 ->[loop above] 5;
6 ->[loop above] 6;

};

\end{tikzpicture}

习题四 31

解:

• (1)
  \begin{tikzpicture}[node distance=10pt]
  \node[draw, circle] (4) {4};
  \node[draw, circle, below=of 4] (2) {2};
  \node[draw, circle, right=20pt of 2] (3) {3};
  \node[draw, circle, below=of 2] (1) {1};

  \graph{
      (4) -- (2) -- (1);
      (3) -- (1)
  };
  

  \end{tikzpicture}

  (2)
  \begin{tikzpicture}[node distance=10pt]
  \node[draw, circle] (36) {36};
  \node[draw, circle, below=of 36] (12) {12};
  \node[draw, circle, below=of 12] (6) {6};
  \node[draw, circle, below=of 6] (3) {3};
  \node[draw, circle, right=20pt of 3] (2) {2};
  \node[draw, circle, right=20pt of 6] (26) {26};

  \graph{
      (36) -- (12) -- (6) -- (3);
      (6) -- (2);
      (26) -- (2);
  };
  

  \end{tikzpicture}

  (3)
  \begin{tikzpicture}[node distance=15pt]
  \node[draw, circle] (8) {8};
  \node[draw, circle, right=20pt of 8] (12) {12};
  \node[draw, circle, below=of 12] (6) {6};
  \node[draw, circle, below=of 8] (4) {4};
  \node[draw, circle, below=of 6] (3) {3};
  \node[draw, circle, below=of 4] (2) {2};
  \node[draw, circle, right=20pt of 3] (5) {5};
  \node[draw, circle, right=20pt of 5] (7) {7};
  \node[draw, circle, right=20pt of 7] (11) {11};
  \node[draw, circle, right=20pt of 6] (9) {9};
  \node[draw, circle, below=of 3] (1) {1};

  \graph{
      (8) -- (4) -- (2) -- (1);
      (12) -- (6) -- (3) -- (1);
      (12) -- (4);
      (6) -- (2);
      (9) -- (3);
      (1) -- {
          (5),(7),(11)
      }
  };
  

  \end{tikzpicture}

  \(\{2,3,6\}:6,\text{无},6,\{2,3\},6,1\).

  \(\{2,4,6\}:\text{无},2,\{4,6\},2,\text{无},2\).

  \(\{4,8,12\}:\text{无},4,\{8,12\},4,4,\text{无}\).

习题四 32

解:

• \(A=\{0,1,2,3,4,5,6\}\).

  \(\preceq=\{(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(1,1),\\(2,2),(2,5),(3,3),(3,5),(5,5),(4,4),(4,6),(6,6)\}\).

习题四 34

证明

• 自反: \(\forall (a,b) \in A\times B\) 由 \((a,a) \in \preceq_1 \wedge (b,b) \in \preceq_2 \Rightarrow ((a,b),(a,b)) \in \preceq_3\).

  反对称: \(\forall ((a_1,b_1),(a_2,b_2)) \in \preceq_3 \wedge ((a_2,b_2),(a_1,b_1)) \in \preceq_3, \\ (a_1,a_2),(a_2,a_1) \in \preceq_1 \wedge (b_1,b_2),(b_2,b_1) \in \preceq_2 \Rightarrow a_1=a_2\wedge b_1=b_2 \Rightarrow (a_1,b_1)=(a_2,b_2)\).

  传递: \(\forall ((a_1,b_1),(a_2,b_2)),((a_2,b_2),(a_3,b_3)) \in \preceq_3, (a_1,a_2),(a_2,a_3) \in \preceq_1, \\ \Rightarrow (a_1,a_3)\in \preceq_1\) 同理 \((b_1,b_3) \in \preceq_2 \Rightarrow ((a_1,b_1),(a_3,b_3)) \in \preceq_3\).

  综上 \(\preceq_3\) 是 \(A\times B\) 上的半序关系.

习题四 37

解:

• (1) 半序
  (2) 良序
  (3) 良序